//
//  NumTilePossibilities.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/6/25.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  1079. 活字印刷

import UIKit

/*
 
 你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

 注意：本题中，每个活字字模只能使用一次。

  

 示例 1：

 输入："AAB"
 输出：8
 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
 
 
 示例 2：

 输入："AAABBC"
 输出：188
  

 提示：

 1 <= tiles.length <= 7
 tiles 由大写英文字母组成
 */

class NumTilePossibilities: NSObject {

    var resultArr:[String] = []
    
    func numTilePossibilities(_ tiles: String) -> Int {

        var sourceArr:[String] = []
        
        for s in tiles.enumerated(){
            sourceArr.append(String(s.element))
        }
        
        let sourceArrSorted = sourceArr.sorted()
        
        let boolArr = Array.init(repeating: false, count: sourceArr.count)
        
        self.dfs(0, [], sourceArrSorted, boolArr)

        return resultArr.count - 1
    }
    
    func dfs(_ startIndex:Int, _ tmpArr:[String], _ sourceArr:[String], _ flagArr:[Bool]){
        
        var arr = tmpArr
        var flagArr = flagArr
        
        let string = tmpArr.joined(separator: "")
        
        //contains()方法极其浪费时间
       // if resultArr.contains(string) == false{
            resultArr.append(string)
            //print(string)
       // }

        if startIndex == sourceArr.count {
            return
        }
        
        for index in 0 ..< sourceArr.count{
            if flagArr[index] == true {
                continue
            }
            //在此处去重即可  不要使用contains()
            if index > 0 && sourceArr[index] == sourceArr[index-1] && flagArr[index-1] == false {
                continue
            }
            
            flagArr[index] = true
            arr.append(sourceArr[index])
            self.dfs(startIndex+1, arr, sourceArr, flagArr)
            
            flagArr[index] = false
            arr.removeLast()
        }
    }
}
